class DicTree:
    def __init__(self):
        self.children = {}
        self.wordIndex = set()
        self.restWorld = {}

    def put(self, word, index):
        if len(word) == 0:
            self.wordIndex.add(index)
            return
        self.restWorld[index] = word
        letter = word[0]
        if letter not in self.children:
            self.children[letter] = DicTree()
        self.children[letter].put(word[1:], index)

    def get(self, word):
        if len(word) == 0:
            r = self.wordIndex.copy()
            for index in self.restWorld:
                if self.isPalindrome(self.restWorld[index]):
                    r.add(index)
            return r
        r = set()
        if len(self.wordIndex) > 0 and self.isPalindrome(word):
            r = self.wordIndex.copy()

        letter = word[0]
        if letter in self.children:
            r1 = self.children[letter].get(word[1:])
            r = r.union(r1)
        return r

    def isPalindrome(self, word):
        for j in range(len(word) // 2):
            if word[j] != word[len(word) - j - 1]:
                return False
        return True


class Solution:
    def palindromePairs(self, words):
        dt = DicTree()
        r = []
        for i in range(len(words)):
            dt.put(words[i], i)
        for i in range(len(words)):
            re = dt.get(words[i][::-1])
            for index in re:
                if index != i:
                    r.append([index, i])
        return r


if __name__ == '__main__':
    so = Solution()
    words = ["lls","s","sssll"]
    r = so.palindromePairs(words)
    print(r)
